class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
		//以二维数组记录改下表出数字结尾的最长子序列和出现的次数
        int[][] f = new int[n][2];
        for(int i=0; i<n; i++){
            f[i][0]=1;
            f[i][1]=1;
            for(int j=0; j<i; j++){
				//最长子序列=之前出现过的小于等于当前数字结尾的最长子序列+1，
				//最长子序列出现次数=所有之前出现过的小于等于当前数字结尾的最长子序列次数的和
                if(nums[i]>nums[j]){
                    if(f[i][0]<f[j][0]+1){
                        f[i][0]=f[j][0]+1;
                        f[i][1]=f[j][1];
                    }else if(f[i][0]==f[j][0]+1){
                        f[i][1]+=f[j][1];
                    }
                }
            }
        }
        int ans = 0;
		//记录每个数字结尾的最长子序列长度和其对应的下标
        Map<Integer,List<Integer>> map = new HashMap<>();
        for(int i=0; i<f.length; i++){
            if(ans<=f[i][0]){
                ans = f[i][0];
                List<Integer> res = map.getOrDefault(ans, new ArrayList<Integer>());
                res.add(i);
                map.put(ans, res);
            }
        }
        int m = 0;
		//取出所有最长子序列的和并相加
        for(Integer i : map.get(ans)){
            m+=f[i][1];
        }
        return m;
    }
}